package Year22_Month03.day29;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.nextLine();
            int left = 0;
            int right = 0;
            char[] arr = str.toCharArray();
            int count = 0;
            for (int i = 0; i < arr.length; i++) {
                int count1 = 0;
                if('0' <= arr[i] && arr[i] <= '9'){
                    left = i;
                }
                while(i < arr.length && '0' <= arr[i] && arr[i] <= '9'){
                    i++;
                    count1++;
                }
                if(count1 > count){
                    right = i;
                }
            }
            System.out.println(str.substring(left,right));
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,5,1,6,2,7,3,8};
        System.out.println(GetLeastNumbers_Solution(arr,8));
    }


    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    public static void shiftDown(int[] arr,int size,int parent){//size是边界，就是向下调整的最后一个可调整的节点的位置
        int child = parent * 2 + 1;
        while(child < size){
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child += 1;
            }
            //接下来进行交换，并且
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
    public static void heapSort(int[] arr){
        int size = arr.length;
        for(int root = (arr.length-2)/2; root >= 0; root--){
            shiftDown(arr, arr.length, root);
        }
        int end = size - 1;
        while(end != 0){
            swap(arr,0,end);
            shiftDown(arr,end,0);
            end--;
        }
    }
    public static  ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> myarr = new ArrayList<>();
        if(input == null){
            return myarr;
        }
        heapSort(input);
        for (int i = 0; i < k; i++) {
            myarr.add(input[i]);
        }
        return myarr;
    }
}
